package com.gitee.wsl.ext.base

import com.gitee.wsl.ext.base.Arrays.arraycopy
import com.gitee.wsl.ext.base.Arrays.fill
import com.gitee.wsl.mathematics.function.Kgcd
import com.gitee.wsl.mathematics.function.random.SecureRandom
import com.ionspin.kotlin.bignum.decimal.BigDecimal.Companion.fromDouble
import com.ionspin.kotlin.bignum.decimal.BigDecimal.Companion.fromFloat
import com.ionspin.kotlin.bignum.integer.BigInteger
import com.ionspin.kotlin.bignum.integer.Sign
import com.ionspin.kotlin.bignum.integer.Sign.NEGATIVE
import com.ionspin.kotlin.bignum.integer.Sign.POSITIVE
import com.ionspin.kotlin.bignum.integer.toBigInteger



fun BigInteger.toInt() = intValue()
fun BigInteger.toShort() = shortValue()
fun BigInteger.toLong() = longValue()
fun BigInteger.toByte() = byteValue()
fun BigInteger.toFloat() = floatValue()
fun BigInteger.toDouble() = doubleValue()

fun BigInteger.toUInt() = uintValue()
fun BigInteger.toUShort() = ushortValue()
fun BigInteger.toULong() = ulongValue()

fun BigInteger.Companion.valueOf(uLong: ULong) = fromULong(uLong)
fun BigInteger.Companion.valueOf(value: UInt) = fromUInt(value)
fun BigInteger.Companion.valueOf(value: UShort) = fromUShort(value)
fun BigInteger.Companion.valueOf(value: UByte) = fromUByte(value)
fun BigInteger.Companion.valueOf(value: Long) = fromLong(value)
fun BigInteger.Companion.valueOf(value: Int) = fromInt(value)
fun BigInteger.Companion.valueOf(value: Short) = fromShort(value)
fun BigInteger.Companion.valueOf(value: Byte) = fromByte(value)
fun BigInteger.Companion.valueOf(value: Float) = fromFloat(value)
fun BigInteger.Companion.valueOf(value: Double) = fromDouble(value)

fun BigInteger.Companion.valueOf(value: ByteArray,singValue:Int) = fromByteArray(value,when(singValue){
     1 -> POSITIVE
     -1-> NEGATIVE
     0 -> Sign.ZERO
    else -> throw IllegalArgumentException("singValue not support")
})


/**
 * 换字节流（字节数组）型数据转大数字
 *
 * @return BigInteger
 */
fun ByteArray.toBigInteger() : BigInteger{
    if (this[0] < 0) {
        val temp = ByteArray(size + 1)
        temp[0] = 0
        arraycopy(this, 0, temp, 1, size)
        return BigInteger.fromByteArray(temp,Sign.POSITIVE)
    }
    return BigInteger.fromByteArray(this,Sign.POSITIVE)
}

private const val MAX_ITERATIONS = 1000

/**
 * Return the passed in value as an unsigned byte array.
 *
 * @param value the value to be converted.
 * @return a byte array without a leading zero byte if present in the signed encoding.
 */
fun asUnsignedByteArray(
    value: BigInteger,
): ByteArray {
    val bytes = value.toByteArray()

    if (bytes[0].toInt() == 0 && bytes.size != 1) {
        val tmp = ByteArray(bytes.size - 1)

        arraycopy(bytes, 1, tmp, 0, tmp.size)

        return tmp
    }

    return bytes
}

/**
 * Return the passed in value as an unsigned byte array of the specified length, padded with
 * leading zeros as necessary..
 *
 * @param length the fixed length of the result
 * @param value  the value to be converted.
 * @return a byte array padded to a fixed length with leading zeros.
 */
fun asUnsignedByteArray(length: Int, value: BigInteger): ByteArray {
    val bytes = value.toByteArray()
    if (bytes.size == length) {
        return bytes
    }

    val start = if (bytes[0].toInt() == 0 && bytes.size != 1) 1 else 0
    val count = bytes.size - start

    require(count <= length) { "standard length exceeded for value" }

    val tmp = ByteArray(length)
    arraycopy(bytes, start, tmp, tmp.size - count, count)
    return tmp
}

/**
 * Write the passed in value as unsigned bytes to the specified buffer range, padded with
 * leading zeros as necessary.
 *
 * @param value the value to be converted.
 * @param buf   the buffer to which the value is written.
 * @param off   the start offset in array `buf` at which the data is written.
 * @param len   the fixed length of data written (possibly padded with leading zeros).
 */
fun asUnsignedByteArray(value: BigInteger, buf: ByteArray, off: Int, len: Int) {
    val bytes = value.toByteArray()
    if (bytes.size == len) {
        arraycopy(bytes, 0, buf, off, len)
        return
    }

    val start = if (bytes[0].toInt() == 0 && bytes.size != 1) 1 else 0
    val count = bytes.size - start

    require(count <= len) { "standard length exceeded for value" }

    val padLen = len - count
    fill(buf, off, off + padLen, 0x00.toByte())
    arraycopy(bytes, start, buf, off + padLen, count)
}


/**
 * Return a random BigInteger not less than 'min' and not greater than 'max'
 *
 * @param min    the least value that may be generated
 * @param max    the greatest value that may be generated
 * @param random the source of randomness
 * @return a random BigInteger value in the range [min,max]
 */
fun BigInteger.Companion.createRandomInRange(
    min: BigInteger,
    max: BigInteger,
    random: SecureRandom,
): BigInteger {
    val cmp = min.compareTo(max)
    if (cmp >= 0) {
        require(cmp <= 0) { "'min' may not be greater than 'max'" }

        return min
    }

    if (min.bitLength() > max.bitLength() / 2) {
        return createRandomInRange(BigInteger.ZERO, max.subtract(min), random).add(min)
    }

    for (i in 0..<MAX_ITERATIONS) {
        val x = BigInteger.createRandomBigInteger(max.bitLength(), random)
        if (x >= min && x <= max) {
            return x
        }
    }

    // fall back to a faster (restricted) method
    return BigInteger.createRandomBigInteger(max.subtract(min).bitLength() - 1, random).add(min)
}


fun BigInteger.Companion.fromUnsignedByteArray(buf: ByteArray): BigInteger {
    return BigInteger.fromByteArray(buf, Sign.POSITIVE)
}

fun BigInteger.Companion.fromUnsignedByteArray(buf: ByteArray, off: Int, length: Int): BigInteger {
    var mag: ByteArray = buf
    if (off != 0 || length != buf.size) {
        mag = ByteArray(length)
        arraycopy(buf, off, mag, 0, length)
    }
    return BigInteger.fromByteArray(mag, Sign.POSITIVE)
}

fun byteValueExact(x: BigInteger): Byte {
    // Since Java 1.8 could use BigInteger.byteValueExact instead
    if (x.bitLength() > 7) {
        throw ArithmeticException("BigInteger out of int range")
    }

    return x.byteValue()
}

fun shortValueExact(x: BigInteger): Short {
    // Since Java 1.8 could use BigInteger.shortValueExact instead
    if (x.bitLength() > 15) {
        throw ArithmeticException("BigInteger out of int range")
    }

    return x.shortValue()
}

fun intValueExact(x: BigInteger): Int {
    // Since Java 1.8 could use BigInteger.intValueExact instead
    if (x.bitLength() > 31) {
        throw ArithmeticException("BigInteger out of int range")
    }

    return x.intValue()
}

fun longValueExact(x: BigInteger): Long {
    // Since Java 1.8 could use BigInteger.longValueExact instead
    if (x.bitLength() > 63) {
        throw ArithmeticException("BigInteger out of long range")
    }

    return x.longValue()
}
//
//fun modOddInverse(M: BigInteger, X: BigInteger): BigInteger {
//    var X = X
//    require(M.testBit(0)) { "'M' must be odd" }
//    if (M.signum() != 1) {
//        throw ArithmeticException("BigInteger: modulus not positive")
//    }
//    if (X.signum() < 0 || X.bitLength() > M.bitLength()) {
//        X = X.mod(M)
//    }
//
//    val bits = M.bitLength()
//    val m: IntArray = Nat.fromBigInteger(bits, M)
//    val x: IntArray? = Nat.fromBigInteger(bits, X)
//    val len = m.size
//    val z: IntArray? = Nat.create(len)
//    if (0 == Mod.modOddInverse(m, x, z)) {
//        throw ArithmeticException("BigInteger not invertible.")
//    }
//    return Nat.toBigInteger(len, z)
//}
//
//fun modOddInverseVar(M: BigInteger, X: BigInteger): BigInteger {
//    var X = X
//    require(M.testBit(0)) { "'M' must be odd" }
//    if (M.signum() != 1) {
//        throw ArithmeticException("BigInteger: modulus not positive")
//    }
//    if (M.equals(ONE)) {
//        return ZERO
//    }
//    if (X.signum() < 0 || X.bitLength() > M.bitLength()) {
//        X = X.mod(M)
//    }
//    if (X.equals(ONE)) {
//        return ONE
//    }
//
//    val bits = M.bitLength()
//    val m: IntArray = Nat.fromBigInteger(bits, M)
//    val x: IntArray? = Nat.fromBigInteger(bits, X)
//    val len = m.size
//    val z: IntArray? = Nat.create(len)
//    if (!Mod.modOddInverseVar(m, x, z)) {
//        throw ArithmeticException("BigInteger not invertible.")
//    }
//    return Nat.toBigInteger(len, z)
//}
//
//fun modOddIsCoprime(M: BigInteger, X: BigInteger): Boolean {
//    var X = X
//    require(M.testBit(0)) { "'M' must be odd" }
//    if (M.signum() != 1) {
//        throw ArithmeticException("BigInteger: modulus not positive")
//    }
//    if (X.signum() < 0 || X.bitLength() > M.bitLength()) {
//        X = X.mod(M)
//    }
//
//    val bits = M.bitLength()
//    val m: IntArray? = Nat.fromBigInteger(bits, M)
//    val x: IntArray? = Nat.fromBigInteger(bits, X)
//    return 0 != Mod.modOddIsCoprime(m, x)
//}
//
//fun modOddIsCoprimeVar(M: BigInteger, X: BigInteger): Boolean {
//    var X = X
//    require(M.testBit(0)) { "'M' must be odd" }
//    if (M.signum() !== 1) {
//        throw ArithmeticException("BigInteger: modulus not positive")
//    }
//    if (X.signum() < 0 || X.bitLength() > M.bitLength()) {
//        X = X.mod(M)
//    }
//    if (X.equals(ONE)) {
//        return true
//    }
//
//    val bits = M.bitLength()
//    val m: IntArray? = Nat.fromBigInteger(bits, M)
//    val x: IntArray? = Nat.fromBigInteger(bits, X)
//    return Mod.modOddIsCoprimeVar(m, x)
//}

fun getUnsignedByteLength(n: BigInteger): Int {
    if (n.equals(BigInteger.ZERO)) {
        return 1
    }

    return (n.bitLength() + 7) / 8
}

/**
 * Return a positive BigInteger in the range of 0 to 2**bitLength - 1.
 *
 * @param bitLength maximum bit length for the generated BigInteger.
 * @param random    a source of randomness.
 * @return a positive BigInteger
 */
fun BigInteger.Companion.createRandomBigInteger(bitLength: Int, random: SecureRandom): BigInteger {
    return BigInteger.fromByteArray(createRandom(bitLength, random), Sign.POSITIVE)
}

val BigInteger.Companion.THREE get() = BigInteger.ONE + BigInteger.TWO

@Throws(IllegalArgumentException::class)
private fun createRandom(bitLength: Int, random: SecureRandom): ByteArray {
    require(bitLength >= 1) { "bitLength must be at least 1" }

    val nBytes = (bitLength + 7) / 8

    val rv = ByteArray(nBytes)

    random.nextBytes(rv)

    // strip off any excess bits in the MSB
    val xBits = 8 * nBytes - bitLength
    rv[0] = (rv[0].toInt() and (255 ushr xBits).toByte().toInt()).toByte()

    return rv
}
//
// class Cache: SynchronizedObject() {
//    private val values = HashMap<BigInteger, Boolean>()
//    private val preserve = arrayOfNulls<BigInteger>(8)
//
//    private var preserveCounter = 0
//
//
//    fun add(value: BigInteger)= synchronized(this) {
//        values.put(value, true)
//        preserve[preserveCounter] = value
//        preserveCounter = (preserveCounter + 1) % preserve.size
//    }
//
//
//    fun contains(value: BigInteger?): Boolean= synchronized(this) {
//        return values.containsKey(value)
//    }
//
//
//    fun size(): Int = synchronized(this){
//        return values.size
//    }
//
//
//    fun clear() = synchronized(this){
//        values.clear()
//        for (i in preserve.indices) {
//            preserve[i] = null
//        }
//    }
//}


fun BigInteger.modPow(exponent: BigInteger, modulus: BigInteger): BigInteger {
    var result = BigInteger.ONE
    var baseMod = this % modulus
    var exp = exponent

    while (exp > BigInteger.ZERO) {
        if (exp % BigInteger.TWO == BigInteger.ONE) {
            result = (result * baseMod) % modulus
        }
        exp /= BigInteger.TWO
        baseMod = (baseMod * baseMod) % modulus
    }

    return result
}


// this = p
fun BigInteger.phi(q: BigInteger) = (this - ONE) * (q - ONE)

fun BigInteger.lcm(other: BigInteger) = this * other / gcd(other)

fun BigInteger.mutualPrime(other: BigInteger) = gcd(other) == ONE

// this = e
fun BigInteger.invert(phi: BigInteger): BigInteger = modInverse(phi)

fun BigInteger.gcdExt(other: BigInteger) = Kgcd.gcdext(this, other)

// this = c
//fun BigInteger.decrypt2String(d: BigInteger, n: BigInteger): String =
//    with(modPow(d, n).n2s()) {
//        REG_NON_PRINTABLE.find(this)?.run { modPow(d, n).toString() } ?: this
//    }

//fun BigInteger.decrypt(d: BigInteger, n: BigInteger): BigInteger = modPow(d, n)
//
//fun BigInteger.n2s() = toByteArray().decodeToString()
//
//fun String.s2n() = BigInteger(toByteArray())




fun List<BigInteger>.phi(): BigInteger =
    filter { it > BigInteger.ZERO }
        .groupBy { it }
        .map { it.key.eulerPhi(it.value.size) }
        .reduce { acc, phi -> acc * phi }

fun List<BigInteger>.phiMutualPrime(e: BigInteger): List<BigInteger> = filter {
    it > BigInteger.ZERO && e.gcd(it.minus(ONE)) == ONE
}

fun List<BigInteger>.product(): BigInteger = reduce { acc, int -> acc * int }

fun List<BigInteger>.propN(n: BigInteger) =
    filter { it < BigInteger.ZERO }.fold(n) { acc, bigInteger -> acc / bigInteger.abs() }

fun BigInteger.eulerPhi(n: Int) = if (n == 1) minus(ONE) else minus(ONE) * pow(n - 1)

// this = n
//fun BigInteger.factorDb() = getPrimeFromFactorDb(this)

//fun getPrimeFromFactorDb(digit: BigInteger) = getPrimeFromFactorDb(digit.toString())
//
//fun getPrimeFromFactorDb(digit: String): List<BigInteger> {
//    return runCatching {
//        "http://factordb.com/api?query=$digit"
//            .readFromNet(timeout = 3000)
//            .fromJson(FactorDbResponse::class.java)
//            .factorList
//    }
//        .getOrElse { mutableListOf(digit.toBigInteger().negate()) }
//}

// ported from
// https://github.com/ryanInf/python2-libnum/blob/316c378ba268577320a239b2af0d766c1c9bfc6d/libnum/common.py
fun BigInteger.root(n: Int = 2): Array<BigInteger> {
    require(n > 0) { "n must be > 0" }
    require(signum() >= 0 || (signum() < 0 && n % 2 != 0)) { "$this  n =$n must be even" }

    val sig = this.signum()
    val v = this.abs()
    var high = ONE
    while (high.pow(n) <= v) high = high.shiftLeft(1)
    var low = high.shiftRight(1)
    var mid = ONE
    var midCount = 0
    while (low < high) {
        mid = (low + high).shiftRight(1)
        if (low < mid && mid.pow(n) <= v) {
            low = mid
        } else if (high > mid && mid.pow(n) >= v) high = mid else mid.also { midCount++ }
        if (midCount > 1) break
    }
    return with(mid * sig.toBigInteger()) { arrayOf(this, this@root - this.pow(n)) }
}

fun BigInteger.shiftLeft(num:Int) = this shl num

fun BigInteger.shiftRight(num:Int) = this shr num


/** 连分数 */
fun BigInteger.continuedFraction(another: BigInteger): MutableList<BigInteger> {
    var a = this
    val list = mutableListOf<BigInteger>()
    var b = another
    while (b != BigInteger.ZERO) {
        list.add(a / b)
        a = b.also { b = a % b }
    }
    return list
}

/** 渐进分数线 */
fun List<BigInteger>.convergent(): MutableList<Pair<BigInteger, BigInteger>> {
    var (pbe, paf) = BigInteger.ZERO to ONE
    var (qbe, qaf) = ONE to BigInteger.ZERO
    val convergent = mutableListOf<Pair<BigInteger, BigInteger>>()
    for (int in this) {
        pbe = paf.also { paf = int * paf + pbe }
        qbe = qaf.also { qaf = int * qaf + qbe }
        convergent.add(paf to qaf)
    }
    return convergent
}

/** this is e, common wiener, but it's too slow */
@Suppress("ReturnCount")
fun BigInteger.wiener(n: BigInteger): BigInteger? {
    println("wiener attack-")
    val wienerPQ = wienerPQ(n)
    if (wienerPQ != null) {
        return wienerPQ
    }
    println("wiener attack slow")
    var q0 = ONE
    val m = TWO
    val c1 = m.modPow(this, n)
    val convergent = this.continuedFraction(n).convergent()
    for ((_, q1) in convergent) {
        for (r in 0..20) for (s in 0..20) {
            val d = r.toBigInteger() * q1 + s.toBigInteger() * q0
            val m1 = c1.modPow(d, n)
            if (m1 == m) {
                println("$r $s $d")
                return d
            }
        }
        q0 = q1
    }
    return null
}

/** this is e ,n = p *q */
fun BigInteger.wienerPQ(n: BigInteger): BigInteger? {
    println("wiener attack pq")
    if (this > n.pow(2).multiply(n.root().first())) {
        println("e > n^(1.5) -> this is not guaranteed to work")
    }
    var x = this
    var y = n
    var guessK: BigInteger
    var guessDg: BigInteger
    val guessD: BigInteger
    // val pMinusQDiv2: BigInteger
    // i = 0
    // q[0] = [e/n]
    // n[0] = q[0]
    // d[0] = 1
    val q0 = x / y
    val n0 = q0
    val d0 = ONE
    var temp = x
    x = y
    y = temp.add(y.multiply(q0).negate())

    // i = 1
    // q[1] = [n / (e - n * [e/n])]
    // n[1] = q[0] * q[1] + 1
    // d[1] = q[1]
    var qI = x / y
    val n1 = q0 * qI + ONE
    val d1 = qI
    // i = 2
    var dI2 = d0
    var dI1 = d1
    var dI: BigInteger
    var nI2 = n0
    var nI1 = n1
    var nI: BigInteger
    var i = 1
    val startTime = currentTimeMillis
    while (x.add(-y * qI).signum() != 0 && (currentTimeMillis - startTime) < 500) {
        // uncomment for debug
        //        println("q[$i] = $qI")
        //        println("n[$i] = $nI")
        //        println("d[$i] = $dI")
        i++
        temp = x
        x = y
        y = temp.add(-y * qI)
        qI = x / y

        // d[i] = q[i] * d[i-1] + d[i-2]
        // n[i] = q[i] * n[i-1] + n[i-2]
        dI = qI * dI1 + dI2
        nI = qI * nI1 + nI2
        dI2 = dI1
        dI1 = dI
        nI2 = nI1
        nI1 = nI

        if (i % 2 == 0) {
            // k / dg = <q[0],...,q[i-1],q[i]+1>
            // k = (q[i] + 1) * n[i-1] + n[i-2]
            guessK = nI1 + nI2
            // dg = (q[i] + 1) * d[i-1] + d[i-2]
            guessDg = dI1 + dI2
        } else {
            // k / dg = <q[0],...,q[i-1],q[i]>
            // k = q[i] * n[i-1] + n[i-2]
            guessK = nI1
            // dg = q[i] * d[i-1] + d[i-2]
            guessDg = dI1
        }

        // phi(n) = (edg) / k
        val phiN = this * guessDg / guessK
        // (p+q)/2 = (pq - (p-1)*(q-1) + 1)/2
        val pPlusQDiv2 = (n - phiN + ONE) / TWO
        val subtract = pPlusQDiv2.pow(2).subtract(n)
        if (subtract < BigInteger.ZERO) break
        val root = subtract.root()
        if (root.last() == BigInteger.ZERO) {
            // ((p-q)/2)^2 = ((p+q)/2)^2 - pq
            // pMinusQDiv2 = root.first()
            // d = (dg / g) = dg / (edg mod k)
            guessD = guessDg / ((this * guessDg) % guessK)
            // (p+q)/2 = (pq - (p-1)*(q-1) + 1)/2
            //            val guessP = pPlusQDiv2 + pMinusQDiv2
            // q = (p+q)/2 - (p-q)/2
            //            val guessQ = pPlusQDiv2 - pMinusQDiv2
            println("Success")
            return guessD
        }
    }
    return null
}

/** 乘法逆元 (n * m) % p == 1. m = n^-1 =n % p */
fun BigInteger.multiplyInverse(modular: BigInteger): BigInteger {
    val (gcd, x, _) = gcdExt(modular)
    require(gcd == ONE) { "has no multiplicative inverse" }
    return x.mod(modular)
}


//fun BigInteger.random(from: BigInteger = ONE): BigInteger {
//    val bits = bitLength()
//    var r = BigInteger(bits, Random)
//    while (r < from || r > this) {
//        r = BigInteger(bits, Random)
//    }
//    return r
//}

val ONE = BigInteger.ONE

val TWO = BigInteger.TWO

val THREE = BigInteger.THREE

val FOUR = 4.toBigInteger()
val FIVE = 5.toBigInteger()
val SIX = 6.toBigInteger()
val SEVEN = 7.toBigInteger()
val EIGHT = 8.toBigInteger()

val MAP = mapOf(THREE to TWO, FOUR to THREE, FIVE to THREE, SIX to FIVE, SEVEN to FIVE)

/** todo performance */
//fun BigInteger.preProbablePrime(): BigInteger {
//    if (this < EIGHT) return MAP[this]!!
//    var pre: BigInteger
//    val nn = (this / SIX) * SIX
//    if (this - nn <= ONE) {
//        pre = nn - ONE
//        if (pre.isProbablePrime(100)) {
//            return pre
//        }
//        pre -= FOUR
//    } else {
//        pre = nn + ONE
//    }
//    while (true) {
//        if (pre.isProbablePrime(100)) break
//        pre -= TWO
//        if (pre.isProbablePrime(100)) break
//        pre -= FOUR
//    }
//
//    return pre
//}

//fun BigInteger.isProbablePrime(certainty:Int):Boolean{
//    return this.
//}

 fun <T> Iterable<T>.sumOf(selector: (T) -> BigInteger): BigInteger {
    var sum = 0.toBigInteger()
    for (element in this) {
        sum = sum + selector(element)
    }
    return sum
}